import java.util.HashMap;

/**
 * @author VernHe
 * @date 2021年06月07日 19:25
 */
class LRUCache {
    // 内部类，组成lru链表
    class Node {
        public int key, val;
        public Node next, prev;
        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
    // 用于查找元素
    HashMap<Integer, Node> map = new HashMap<>();
    // 头节点和尾结点处于链表的两端，不需要担心链表中node.next或者node.prev为null
    Node head, tail;
    // lru链表容量
    int capacity;
    // 构造器，用于初始化变量
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // 有就返回，并移动到前面去
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 将node移动到前面
            refresh(node);
            return node.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node;
        // 已经存在,覆盖
        if (map.containsKey(key)) {
            node = map.get(key);
            node.val = value;
        } else {
            // 不存在，就进行添加
            // 检查是否满了
            if (capacity == map.size()) {
                // map和链表中删除最后一个节点（tail前面的那个节点），然后放入新元素
                map.remove(tail.prev.key);
                deleteNode(tail.prev);
            }
            // 放入新元素
            node = new Node(key, value);
            map.put(key, node);
        }
        // 传进去的可能是空
        refresh(node);
    }

    /**
     * 挪动节点到最前面
     * @param node
     */
    private void refresh(Node node) {
        // 从链表中删除，也就是拿出来
        deleteNode(node);
        // 头插法，放到head后面
        node.next = head.next;
        node.prev = head;
        head.next = node;
        node.next.prev = node;
    }

    /**
     * 删除节点
     * @param node
     */
    private void deleteNode(Node node) {
        // 空的就返回
        if (node == null) {
            return;
        }
        // 如果是最后一个节点，就只需要改一个指针
        if (node.next == null) {
            node.prev = null;
            return;
        }
        // 前后指针都要更新
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    void refresh2(Node node) {
        deleteNode(node);
        node.next = head.next;
        node.prev = head;
        head.next = node;
        node.next.prev = node;
    }

    private void deleteNode2(Node node) {
        if (node.next != null) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

}
